Exercise 3 Machine Learning
Read through and follow along with the Machine Learning review with an intro to the tidymodels package posted on the Course Materials page.
Tasks:
1.
Read about the hotel booking data, hotels, on the Tidy Tuesday page it came from. There is also a link to an article from the original authors. The outcome we will be predicting is called is_canceled. Without doing any analysis, what are some variables you think might be predictive and why?
deposit_type might be predictive since if the pay is non-refundable, the customer would be less inclined to cancel because they don’t want to waste their money.
lead_time might be predictive because the more numbers of days there are between the booking time and arrival date, the more likely that some unexpected change might occur in the customers’ schedules.
children and babies might be predictive because if the children or babies get sick or have any other reason so that they cannot travel, it is very likely that parents will cancel the trip.
If there is a difference between reserved_room_type and assigned_room_type, the customer might want to cancel their reservation because they don’t get the room they want.
days_in_waiting_list might be predictive because if the customer needs to wait for a long time to have their reservations confirmed, they might reserve another hotel and cancel the one on the waiting list.
customer_type might also be predictive because if the customer is associated with a group or a contract, it might be harder for then to cancel their booking.
What are some problems that might exist with the data? You might think about how it was collected and who did the collecting.
The authors Antonio, Almeida and Nunes obtained real data from each hotel’s PMS databases and compiled the dataset. The hotels usually use the information the customers provide when they are booking the hotel when they enter these data. So, problems might be that some of the information such as the number of people staying, days they want to stay in this hotel, and special requests might change between the booking and when they check in. However, if a customer cancels their booking, the hotel wouldn’t know if their information would change had they arrived. So, the information for the uncancelled cases might be more accurate then the cancelled cases.
If we construct a model, what type of conclusions will be able to draw from it?
We will be able to see which factors are associated with cancellation, and we can predict the likelihood of cancellation based on these factors. (However, the association might not be causal, so we need to be careful when interpreting the results.)
2.
Create some exploratory plots or table summaries of the data, concentrating most on relationships with the response variable. Keep in mind the response variable is numeric, 0 or 1. You may want to make it categorical (you also may not). Be sure to also examine missing values or other interesting values.
hotels %>%
slice(1:5)
hotels %>%
select(where(is.numeric)) %>%
pivot_longer(cols = everything(),
names_to = "variable",
values_to = "value") %>%
ggplot(aes(x = value)) +
geom_histogram(bins = 30) +
facet_wrap(vars(variable),
scales = "free")

hotels %>%
ggplot(aes(y=lead_time, x=as.factor(is_canceled))) +
geom_boxplot()

hotels %>%
ggplot(aes(x= deposit_type, group=is_canceled)) +
geom_bar(aes(y = ..prop.., fill = factor(..x..)), stat="count") +
geom_text(aes( label = scales::percent(..prop..),
y= ..prop.. ), stat= "count", vjust = -.5) +
labs(y = "Percent", fill="customer_type") +
facet_grid(~is_canceled) +
scale_y_continuous(labels = scales::percent)

hotels %>%
ggplot(aes(x= customer_type, group=is_canceled)) +
geom_bar(aes(y = ..prop.., fill = factor(..x..)), stat="count") +
geom_text(aes( label = scales::percent(..prop..),
y= ..prop.. ), stat= "count", vjust = -.5) +
labs(y = "Percent", fill="customer_type") +
facet_grid(~is_canceled) +
scale_y_continuous(labels = scales::percent)

hotels %>%
filter(days_in_waiting_list > 0) %>%
ggplot(aes(y=days_in_waiting_list, x=as.factor(is_canceled)))+
geom_boxplot()

hotels %>%
add_n_miss() %>%
count(n_miss_all)
3.
First, we will do a couple things to get the data ready, including making the outcome a factor (needs to be that way for logistic regression), removing the year variable and some reservation status variables, and removing missing values (not NULLs but true missing values). Split the data into a training and test set, stratifying on the outcome variable, is_canceled. Since we have a lot of data, we’re going to split the data 50/50 between training and test. I have already set.seed() for you. Be sure to use hotels_mod in the splitting.
hotels_mod <- hotels %>%
mutate(is_canceled = as.factor(is_canceled)) %>%
mutate(across(where(is.character), as.factor)) %>%
select(-arrival_date_year,
-reservation_status,
-reservation_status_date) %>%
add_n_miss() %>%
filter(n_miss_all == 0) %>%
select(-n_miss_all)
set.seed(494)
hotel_split <- initial_split(hotels_mod,
prop = .5)
hotel_split
## <Analysis/Assess/Total>
## <59693/59693/119386>
hotel_training <- training(hotel_split)
hotel_testing <- testing(hotel_split)
4.
In this next step, we are going to do the pre-processing. Usually, I won’t tell you exactly what to do here, but for your first exercise, I’ll tell you the steps.
hotel_recipe <- recipe(is_canceled ~ ., #short-cut, . = all other vars
data = hotel_training) %>%
# Pre-processing:
# Create indicator variables for children, babies, and previous_cancellations
step_mutate_at(children, babies, previous_cancellations,
fn = ~ as.factor((.>0))
) %>%
step_mutate_at(agent, company,
fn = ~ as.factor((.== "NULL"))
) %>%
step_mutate(country = as.character(country),
country = fct_lump_n(country, 5)) %>%
step_normalize(all_predictors(),
-all_nominal()) %>%
step_dummy(all_nominal(),
-all_outcomes())
hotel_recipe %>%
prep(hotel_training) %>%
# using bake(new_data = NULL) gives same result as juice()
# bake(new_data = NULL)
juice()
5.
In this step we will set up a LASSO model and workflow. In general, why would we want to use LASSO instead of regular logistic regression? (HINT: think about what happens to the coefficients).
Because LASSO will select the most significant variables by shrinking the coefficients, and therefore select the subset of variables that maximizes prediction accuracy.
Define the model type, set the engine, set the penalty argument to tune() as a placeholder, and set the mode. Create a workflow with the recipe and model.
hotel_lasso_mod <-
# Define a lasso model
logistic_reg(mixture = 1) %>%
# Set the engine to "glm"
set_engine("glmnet") %>%
# The parameters we will tune.
set_args(penalty = tune()) %>%
# Use "regression"
set_mode("classification")
hotel_lasso_wf <-
# Set up the workflow
workflow() %>%
# Add the recipe
add_recipe(hotel_recipe) %>%
# Add the modeling
add_model(hotel_lasso_mod)
6.
In this step, we’ll tune the model and fit the model using the best tuning parameter to the entire training dataset.
Create a 5-fold cross-validation sample.
# Set seed
set.seed(494) # for reproducibility
# Create a 5-fold cross-validation sample
hotel_cv <- vfold_cv(hotel_training, v = 5)
Use the grid_regular() function to create a grid of 10 potential penalty parameters (we’re keeping this sort of small because the dataset is pretty large). Use that with the 5-fold cv data to tune the model.
penalty_grid <- grid_regular(penalty(),
levels = 10)
Use the tune_grid() function to fit the models with different tuning parameters to the different cross-validation sets.
hotel_lasso_tune <-
hotel_lasso_wf %>%
tune_grid(
resamples = hotel_cv,
grid = penalty_grid
)
Use the collect_metrics() function to collect all the metrics from the previous step and create a plot with the accuracy on the y-axis and the penalty term on the x-axis. Put the x-axis on the log scale.
hotel_lasso_tune %>%
collect_metrics() %>%
filter(.metric == "accuracy")
# Visualize accuracy vs. penalty
hotel_lasso_tune %>%
collect_metrics() %>%
filter(.metric == "accuracy") %>%
ggplot(aes(x = penalty, y = mean)) +
geom_point() +
geom_line() +
scale_x_log10(
breaks = scales::trans_breaks("log10", function(x) 10^x),
labels = scales::trans_format("log10",scales::math_format(10^.x))) +
labs(x = "penalty", y = "rmse")

Use the select_best() function to find the best tuning parameter, fit the model using that tuning parameter to the entire training set (HINT: finalize_workflow() and fit()), and display the model results using pull_workflow_fit() and tidy(). Are there some variables with coefficients of 0?
best_param <- hotel_lasso_tune %>%
select_best(metric = "accuracy")
best_param
hotel_lasso_final_wf <- hotel_lasso_wf %>%
finalize_workflow(best_param)
hotel_lasso_final_mod <- hotel_lasso_final_wf %>%
fit(data = hotel_training)
hotel_lasso_final_mod %>%
pull_workflow_fit() %>%
tidy()
market_segment_Groups, distribution_channel_Undefined, assigned_room_type_L, assigned_room_type_P all have coefficients equal to 0.
7.
Now that we have a model, let’s evaluate it a bit more. All we have looked at so far is the cross-validated accuracy from the previous step.
Create a variable importance graph. Which variables show up as the most important? Are you surprised?
# Visualize variable importance
hotel_lasso_final_mod %>%
pull_workflow_fit() %>%
vip()

I am surprised that reserved_room_type_P is the most important factor, and I am also surprised that in general room type is an important factor, and that a non refundable deposit type actually has a positive coefficient.
Use the last_fit() function to fit the final model and then apply it to the testing data. Report the metrics from the testing data using the collet_metrics() function. How do they compare to the cross-validated metrics?
hotel_lasso_test <- hotel_lasso_final_wf %>%
last_fit(hotel_split)
hotel_lasso_test %>%
collect_metrics()
They are similar to the cross validated metrics.
Use the collect_predictions() function to find the predicted probabilities and classes for the test data. Save this to a new dataset called preds. Then, use the conf_mat() function from dials (part of tidymodels) to create a confusion matrix showing the predicted classes vs. the true classes. What is the true positive rate (sensitivity)? What is the true negative rate (specificity)? See this Wikipedia reference if you (like me) tend to forget these definitions.
preds <- collect_predictions(hotel_lasso_test)
preds %>%
conf_mat(is_canceled, .pred_class)
## Truth
## Prediction 0 1
## 0 34226 7782
## 1 3339 14346
The true positive rate (sensitivity) is \(14032/(14032+8004)\approx 63.68\%\), and the true negative rate (specificity) is \(34493/(34493+3164)\approx 91.60\%\)
Use the preds dataset you just created to create a density plot of the predicted probabilities of canceling (the variable is called .pred_1), filling by is_canceled. Use an alpha = .5 and color = NA in the geom_density(). Answer these questions:
preds %>%
ggplot(aes(x = .pred_1, fill = is_canceled)) +
geom_density(alpha=0.5, color = NA)

a.
What would this graph look like for a model with an accuracy that was close to 1?
The two density curves would be almost separated instead of having a lot of overlapped region.
b.
Our predictions are classified as canceled if their predicted probability of canceling is greater than .5. If we wanted to have a high true positive rate, should we make the cutoff for predicted as canceled higher or lower than .5?
We should make the cutoff higher than 0.5, so that it becomes more likely to predict canceling, and more truly canceled cases would be predicted to be canceled.
c.
What happens to the true negative rate if we try to get a higher true positive rate?
The true negative rate would be lower because more uncanceled cases will be classified as canceled if we try to get a higher true positive rate.
8.
Let’s say that this model is going to be applied to bookings 14 days in advance of their arrival at each hotel, and someone who works for the hotel will make a phone call to the person who made the booking. During this phone call, they will try to assure that the person will be keeping their reservation or that they will be canceling in which case they can do that now and still have time to fill the room. How should the hotel go about deciding who to call? How could they measure whether it was worth the effort to do the calling? Can you think of another way they might use the model?
According to the outcome and VIP of this model, they should call the people who reserve room type P, whose deposit type is non-refundable, and who did have previous cancellations with the hotel. They can also input each customer’s information into the model, and predict whether they would cancel according to the model, and call the people who are predicted to cancel. Also, since reserved room type and assigned room type are both important when determining whether the customer would cancel, the hotel should make a call if they need to change the room type for a customer.
Another way they might use the model is to estimate how many reservations might be canceled for each day, so that they could adjust the number of employees working that day.
9.
How might you go about questioning and evaluating the model in terms of fairness? Are there any questions you would like to ask of the people who collected the data?
I would most likely question the inclusion of country of origin for each customer in this model. I feel like canceling reservations is a more personal thing, and if this model indicates that people from certain countries are more likely to cancel, it would cause false stereotype against people from certain countries when they are booking hotels, and that is not fair.
One question I would like to ask is what measures have they taken to ensure that their sample is general enough and what kind of selection bias might be involve in the data.
Exercise 4 Bias and Fairness
Listen to Dr. Rachel Thomas’s Bias and Fairness lecture. Write a brief paragraph reflecting on it. You might also be interested in reading the ProPublica article Dr. Thomas references about using a tool called COMPAS to predict recidivism. Some questions/ideas you might keep in mind:
Did you hear anything that surprised you?
I was surprised that some big enterprises still practice biased machine learning models when releasing advertisements even after they become aware of the bias that they caused.
Why is it important that we pay attention to bias and fairness when studying data science?
Because it is easy to generalize people and cause stereotype or discrimination against certain groups of people when we use machine learning models. These models are used widely, and if they are misused to cause biases and unfairness, it would hurt many people. Also, bias might arise even when we are collecting data, so we have to acknowledge possible biases that might be caused in our data collection process.
Is there a type of bias Dr. Thomas discussed that was new to you? Can you think about places you have seen these types of biases?
Aggregated bias is new to me. I couldn’t think of an example where I see this type of bias, but I guess a scenario where there exists aggregated bias might be a dataset with different groups where the correlation of the two variables of interest are small within each group, but becomes big in the whole dataset.
LS0tCnRpdGxlOiAnSG9tZXdvcmsgMScKb3V0cHV0OiAKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB0cnVlCiAgICB0b2NfZmxvYXQ6IHRydWUKICAgIGRmX3ByaW50OiBwYWdlZAogICAgY29kZV9kb3dubG9hZDogdHJ1ZQotLS0KCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQprbml0cjo6b3B0c19jaHVuayRzZXQoZWNobyA9IFRSVUUsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0UpCmBgYAoKYGBge3IgbGlicmFyaWVzfQpsaWJyYXJ5KHRpZHl2ZXJzZSkgICAgICAgICAjIGZvciBncmFwaGluZyBhbmQgZGF0YSBjbGVhbmluZwpsaWJyYXJ5KHRpZHltb2RlbHMpICAgICAgICAjIGZvciBtb2RlbGluZwpsaWJyYXJ5KG5hbmlhcikgICAgICAgICAgICAjIGZvciBhbmFseXppbmcgbWlzc2luZyB2YWx1ZXMKbGlicmFyeSh2aXApICAgICAgICAgICAgICAgIyBmb3IgdmFyaWFibGUgaW1wb3J0YW5jZSBwbG90cwpsaWJyYXJ5KGRwbHlyKSAgICAgICAgICAgICAjIGZvciBtYW5pcHVsYXRpbmcgZGF0YXNldHMKbGlicmFyeShnZ3Bsb3QyKSAgICAgICAgICAgIyBmb3IgdmlzdWFsaXphdGlvbnMKYGBgCgpgYGB7cn0KdGhlbWVfc2V0KHRoZW1lX21pbmltYWwoKSkgIyBMaXNhJ3MgZmF2b3JpdGUgdGhlbWUKYGBgCgoKYGBge3IgZGF0YX0KaG90ZWxzIDwtIHJlYWRyOjpyZWFkX2NzdignaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL3Jmb3JkYXRhc2NpZW5jZS90aWR5dHVlc2RheS9tYXN0ZXIvZGF0YS8yMDIwLzIwMjAtMDItMTEvaG90ZWxzLmNzdicpCmBgYAoKCiMjIEV4ZXJjaXNlIDEgR2l0IGFuZCBHaXRodWIKClJlYWQgdGhlIFF1aWNrIEludHJvIHNlY3Rpb24gb2YgdGhlIFVzaW5nIGdpdCBhbmQgR2l0SHViIGluIFIgU3R1ZGlvIHNldCBvZiBDb3Vyc2UgTWF0ZXJpYWxzLiBTZXQgdXAgR2l0IGFuZCBHaXRIdWIgYW5kIGNyZWF0ZSBhIEdpdEh1YiByZXBvIGFuZCBhc3NvY2lhdGVkIFIgUHJvamVjdCAoZG9uZSBmb3IgeW91IHdoZW4geW91IGNsb25lIHRoZSByZXBvKSBmb3IgdGhpcyBob21ld29yayBhc3NpZ25tZW50LiBQdXQgdGhpcyBmaWxlIGludG8gdGhlIHByb2plY3QuIFlvdSBzaG91bGQgYWx3YXlzIG9wZW4gdGhlIFIgUHJvamVjdCAoLlJwcm9qKSBmaWxlIHdoZW4geW91IHdvcmsgd2l0aCBhbnkgb2YgdGhlIGZpbGVzIGluIHRoZSBwcm9qZWN0LgoKKipUYXNrOioqIEJlbG93LCBwb3N0IGEgbGluayB0byB5b3VyIEdpdEh1YiByZXBvc2l0b3J5LgoKaHR0cHM6Ly9naXRodWIuY29tL3NsaTAzMTcvU1RBVDQ5NF9Ib21ld29yay5naXQKCgojIyBFeGVyY2lzZSAyIENyZWF0aW5nIGEgV2Vic2l0ZQpZb3XigJlsbCBiZSB1c2luZyBSU3R1ZGlvIHRvIGNyZWF0ZSBhIHBlcnNvbmFsIHdlYnNpdGUgdG8gc2hvd2Nhc2UgeW91ciB3b3JrIGZyb20gdGhpcyBjbGFzcyEgU3RhcnQgYnkgd2F0Y2hpbmcgdGhlIFNoYXJpbmcgb24gU2hvcnQgTm90aWNlIHdlYmluYXIgYnkgQWxpc29uIEhpbGwgYW5kIERlc2lyw6llIERlIExlb24gb2YgUlN0dWRpby4gVGhpcyBzaG91bGQgaGVscCB5b3UgY2hvb3NlIHRoZSB0eXBlIG9mIHdlYnNpdGUgeW914oCZZCBsaWtlIHRvIGNyZWF0ZS4KCk9uY2UgeW914oCZdmUgY2hvc2VuIHRoYXQsIHlvdSBtaWdodCB3YW50IHRvIGxvb2sgdGhyb3VnaCBzb21lIG9mIHRoZSBvdGhlciBCdWlsZGluZyBhIHdlYnNpdGUgcmVzb3VyY2VzIEkgcG9zdGVkIG9uIHRoZSByZXNvdXJjZXMgcGFnZSBvZiBvdXIgY291cnNlIHdlYnNpdGUuIEkgaGlnaGx5IHJlY29tbWVuZCBtYWtpbmcgYSBuaWNlIGxhbmRpbmcgcGFnZSB3aGVyZSB5b3UgZ2l2ZSBhIGJyaWVmIGludHJvZHVjdGlvbiBvZiB5b3Vyc2VsZi4KCioqVGFza3M6KioKIyMjIGEuCkluY2x1ZGUgYSBsaW5rIHRvIHlvdXIgd2Vic2l0ZSBiZWxvdy4gKElmIGFueW9uZSBkb2VzIG5vdCB3YW50IHRvIHBvc3QgYSB3ZWJzaXRlIHB1YmxpY2x5LCBwbGVhc2UgdGFsayB0byBtZSBhbmQgd2Ugd2lsbCBmaW5kIGEgZGlmZmVyZW50IHNvbHV0aW9uKS4KCmh0dHBzOi8vc2lndW9saS5uZXRsaWZ5LmFwcC8KCiMjIyBiLgpMaXN0ZW4gdG8gYXQgbGVhc3QgdGhlIGZpcnN0IDIwIG1pbnV0ZXMgb2Yg4oCcQnVpbGRpbmcgYSBDYXJlZXIgaW4gRGF0YSBTY2llbmNlLCBDaGFwdGVyIDQ6IEJ1aWxkaW5nIGEgUG9ydGZvbGlv4oCdLiBHbyB0byB0aGUgbWFpbiBwb2RjYXN0IHdlYnNpdGUgYW5kIG5hdmlnYXRlIHRvIGEgcG9kY2FzdCBwcm92aWRlciB0aGF0IHdvcmtzIGZvciB5b3UgdG8gZmluZCB0aGF0IHNwZWNpZmljIGVwaXNvZGUuIFdyaXRlIDItMyBzZW50ZW5jZXMgcmVmbGVjdGluZyBvbiB3aGF0IHRoZXkgZGlzY3Vzc2VkIGFuZCB3aHkgY3JlYXRpbmcgYSB3ZWJzaXRlIG1pZ2h0IGJlIGhlbHBmdWwgZm9yIHlvdS4KCkNyZWF0aW5nIGEgd2Vic2l0ZSBtaWdodCBoZWxwIGVtcGxveWVycyBzZWUgbXkgcGFzdCBwcm9qZWN0cyB3aGVuIEkgYW0gbG9va2luZyBmb3Igam9icyBpbiB0aGUgZnV0dXJlLCBhbmQgYWxzbyBjb25uZWN0IHdpdGggcGVvcGxlIHdobyBoYXZlIHNpbWlsYXIgaW50ZXJlc3RzLiBJdCBhbHNvIGVuYWJsZXMgbWUgdG8gc2hhcmUgbXkgZXhwZXJpZW5jZSBhbmQga25vd2xlZGdlIHdpdGggdGhlIHB1YmxpYywgYW5kIGhlbHAgcGVvcGxlIHdobyB3YW50cyB0byBkbyBzaW1pbGFyIHByb2plY3RzIGFzIHRoZSBwcm9qZWN0cyBkaXNwbGF5ZWQgb24gbXkgd2Vic2l0ZS4KCiMjIyBjLgooT3B0aW9uYWwpIENyZWF0ZSBhbiBSIHBhY2thZ2Ugd2l0aCB5b3VyIG93biBjdXN0b21pemVkIGdwcGxvdDIgdGhlbWUhIFdyaXRlIGEgcG9zdCBvbiB5b3VyIHdlYnNpdGUgYWJvdXQgd2h5IHlvdSBtYWRlIHRoZSBjaG9pY2VzIHlvdSBkaWQgZm9yIHRoZSB0aGVtZS4gU2VlIHRoZSBCdWlsZGluZyBhbiBSIHBhY2thZ2UgYW5kIEN1c3RvbSBnZ3Bsb3QyIHRoZW1lcyByZXNvdXJjZXMuCgoKIyMgRXhlcmNpc2UgMyBNYWNoaW5lIExlYXJuaW5nClJlYWQgdGhyb3VnaCBhbmQgZm9sbG93IGFsb25nIHdpdGggdGhlIE1hY2hpbmUgTGVhcm5pbmcgcmV2aWV3IHdpdGggYW4gaW50cm8gdG8gdGhlIHRpZHltb2RlbHMgcGFja2FnZSBwb3N0ZWQgb24gdGhlIENvdXJzZSBNYXRlcmlhbHMgcGFnZS4KCioqVGFza3M6KioKCiMjIyAxLiAKUmVhZCBhYm91dCB0aGUgaG90ZWwgYm9va2luZyBkYXRhLCBob3RlbHMsIG9uIHRoZSBUaWR5IFR1ZXNkYXkgcGFnZSBpdCBjYW1lIGZyb20uIFRoZXJlIGlzIGFsc28gYSBsaW5rIHRvIGFuIGFydGljbGUgZnJvbSB0aGUgb3JpZ2luYWwgYXV0aG9ycy4gVGhlIG91dGNvbWUgd2Ugd2lsbCBiZSBwcmVkaWN0aW5nIGlzIGNhbGxlZCBpc19jYW5jZWxlZC4KV2l0aG91dCBkb2luZyBhbnkgYW5hbHlzaXMsIHdoYXQgYXJlIHNvbWUgdmFyaWFibGVzIHlvdSB0aGluayBtaWdodCBiZSBwcmVkaWN0aXZlIGFuZCB3aHk/CgpgZGVwb3NpdF90eXBlYCBtaWdodCBiZSBwcmVkaWN0aXZlIHNpbmNlIGlmIHRoZSBwYXkgaXMgbm9uLXJlZnVuZGFibGUsIHRoZSBjdXN0b21lciB3b3VsZCBiZSBsZXNzIGluY2xpbmVkIHRvIGNhbmNlbCBiZWNhdXNlIHRoZXkgZG9uJ3Qgd2FudCB0byB3YXN0ZSB0aGVpciBtb25leS4KCmBsZWFkX3RpbWVgIG1pZ2h0IGJlIHByZWRpY3RpdmUgYmVjYXVzZSB0aGUgbW9yZSBudW1iZXJzIG9mIGRheXMgdGhlcmUgYXJlIGJldHdlZW4gdGhlIGJvb2tpbmcgdGltZSBhbmQgYXJyaXZhbCBkYXRlLCB0aGUgbW9yZSBsaWtlbHkgdGhhdCBzb21lIHVuZXhwZWN0ZWQgY2hhbmdlIG1pZ2h0IG9jY3VyIGluIHRoZSBjdXN0b21lcnMnIHNjaGVkdWxlcy4KCmBjaGlsZHJlbmAgYW5kIGBiYWJpZXNgIG1pZ2h0IGJlIHByZWRpY3RpdmUgYmVjYXVzZSBpZiB0aGUgY2hpbGRyZW4gb3IgYmFiaWVzIGdldCBzaWNrIG9yIGhhdmUgYW55IG90aGVyIHJlYXNvbiBzbyB0aGF0IHRoZXkgY2Fubm90IHRyYXZlbCwgaXQgaXMgdmVyeSBsaWtlbHkgdGhhdCBwYXJlbnRzIHdpbGwgY2FuY2VsIHRoZSB0cmlwLgoKSWYgdGhlcmUgaXMgYSBkaWZmZXJlbmNlIGJldHdlZW4gYHJlc2VydmVkX3Jvb21fdHlwZWAgYW5kIGBhc3NpZ25lZF9yb29tX3R5cGVgLCB0aGUgY3VzdG9tZXIgbWlnaHQgd2FudCB0byBjYW5jZWwgdGhlaXIgcmVzZXJ2YXRpb24gYmVjYXVzZSB0aGV5IGRvbid0IGdldCB0aGUgcm9vbSB0aGV5IHdhbnQuCgpgZGF5c19pbl93YWl0aW5nX2xpc3RgIG1pZ2h0IGJlIHByZWRpY3RpdmUgYmVjYXVzZSBpZiB0aGUgY3VzdG9tZXIgbmVlZHMgdG8gd2FpdCBmb3IgYSBsb25nIHRpbWUgdG8gaGF2ZSB0aGVpciByZXNlcnZhdGlvbnMgY29uZmlybWVkLCB0aGV5IG1pZ2h0IHJlc2VydmUgYW5vdGhlciBob3RlbCBhbmQgY2FuY2VsIHRoZSBvbmUgb24gdGhlIHdhaXRpbmcgbGlzdC4KCmBjdXN0b21lcl90eXBlYCBtaWdodCBhbHNvIGJlIHByZWRpY3RpdmUgYmVjYXVzZSBpZiB0aGUgY3VzdG9tZXIgaXMgYXNzb2NpYXRlZCB3aXRoIGEgZ3JvdXAgb3IgYSBjb250cmFjdCwgaXQgbWlnaHQgYmUgaGFyZGVyIGZvciB0aGVuIHRvIGNhbmNlbCB0aGVpciBib29raW5nLgoKV2hhdCBhcmUgc29tZSBwcm9ibGVtcyB0aGF0IG1pZ2h0IGV4aXN0IHdpdGggdGhlIGRhdGE/IFlvdSBtaWdodCB0aGluayBhYm91dCBob3cgaXQgd2FzIGNvbGxlY3RlZCBhbmQgd2hvIGRpZCB0aGUgY29sbGVjdGluZy4KClRoZSBhdXRob3JzIEFudG9uaW8sIEFsbWVpZGEgYW5kIE51bmVzIG9idGFpbmVkIHJlYWwgZGF0YSBmcm9tIGVhY2ggaG90ZWwncyBQTVMgZGF0YWJhc2VzIGFuZCBjb21waWxlZCB0aGUgZGF0YXNldC4gVGhlIGhvdGVscyB1c3VhbGx5IHVzZSB0aGUgaW5mb3JtYXRpb24gdGhlIGN1c3RvbWVycyBwcm92aWRlIHdoZW4gdGhleSBhcmUgYm9va2luZyB0aGUgaG90ZWwgd2hlbiB0aGV5IGVudGVyIHRoZXNlIGRhdGEuIFNvLCBwcm9ibGVtcyBtaWdodCBiZSB0aGF0IHNvbWUgb2YgdGhlIGluZm9ybWF0aW9uIHN1Y2ggYXMgdGhlIG51bWJlciBvZiBwZW9wbGUgc3RheWluZywgZGF5cyB0aGV5IHdhbnQgdG8gc3RheSBpbiB0aGlzIGhvdGVsLCBhbmQgc3BlY2lhbCByZXF1ZXN0cyBtaWdodCBjaGFuZ2UgYmV0d2VlbiB0aGUgYm9va2luZyBhbmQgd2hlbiB0aGV5IGNoZWNrIGluLiBIb3dldmVyLCBpZiBhIGN1c3RvbWVyIGNhbmNlbHMgdGhlaXIgYm9va2luZywgdGhlIGhvdGVsIHdvdWxkbid0IGtub3cgaWYgdGhlaXIgaW5mb3JtYXRpb24gd291bGQgY2hhbmdlIGhhZCB0aGV5IGFycml2ZWQuIFNvLCB0aGUgaW5mb3JtYXRpb24gZm9yIHRoZSB1bmNhbmNlbGxlZCBjYXNlcyBtaWdodCBiZSBtb3JlIGFjY3VyYXRlIHRoZW4gdGhlIGNhbmNlbGxlZCBjYXNlcy4gCgpJZiB3ZSBjb25zdHJ1Y3QgYSBtb2RlbCwgd2hhdCB0eXBlIG9mIGNvbmNsdXNpb25zIHdpbGwgYmUgYWJsZSB0byBkcmF3IGZyb20gaXQ/CgpXZSB3aWxsIGJlIGFibGUgdG8gc2VlIHdoaWNoIGZhY3RvcnMgYXJlIGFzc29jaWF0ZWQgd2l0aCBjYW5jZWxsYXRpb24sIGFuZCB3ZSBjYW4gcHJlZGljdCB0aGUgbGlrZWxpaG9vZCBvZiBjYW5jZWxsYXRpb24gYmFzZWQgb24gdGhlc2UgZmFjdG9ycy4gKEhvd2V2ZXIsIHRoZSBhc3NvY2lhdGlvbiBtaWdodCBub3QgYmUgY2F1c2FsLCBzbyB3ZSBuZWVkIHRvIGJlIGNhcmVmdWwgd2hlbiBpbnRlcnByZXRpbmcgdGhlIHJlc3VsdHMuKQoKIyMjIDIuCkNyZWF0ZSBzb21lIGV4cGxvcmF0b3J5IHBsb3RzIG9yIHRhYmxlIHN1bW1hcmllcyBvZiB0aGUgZGF0YSwgY29uY2VudHJhdGluZyBtb3N0IG9uIHJlbGF0aW9uc2hpcHMgd2l0aCB0aGUgcmVzcG9uc2UgdmFyaWFibGUuIEtlZXAgaW4gbWluZCB0aGUgcmVzcG9uc2UgdmFyaWFibGUgaXMgbnVtZXJpYywgMCBvciAxLiBZb3UgbWF5IHdhbnQgdG8gbWFrZSBpdCBjYXRlZ29yaWNhbCAoeW91IGFsc28gbWF5IG5vdCkuIEJlIHN1cmUgdG8gYWxzbyBleGFtaW5lIG1pc3NpbmcgdmFsdWVzIG9yIG90aGVyIGludGVyZXN0aW5nIHZhbHVlcy4KCmBgYHtyfQpob3RlbHMgJT4lCiAgc2xpY2UoMTo1KQpgYGAKCgpgYGB7cn0KaG90ZWxzICU+JSAKICBzZWxlY3Qod2hlcmUoaXMubnVtZXJpYykpICU+JSAKICBwaXZvdF9sb25nZXIoY29scyA9IGV2ZXJ5dGhpbmcoKSwKICAgICAgICAgICAgICAgbmFtZXNfdG8gPSAidmFyaWFibGUiLCAKICAgICAgICAgICAgICAgdmFsdWVzX3RvID0gInZhbHVlIikgJT4lIAogIGdncGxvdChhZXMoeCA9IHZhbHVlKSkgKwogIGdlb21faGlzdG9ncmFtKGJpbnMgPSAzMCkgKwogIGZhY2V0X3dyYXAodmFycyh2YXJpYWJsZSksIAogICAgICAgICAgICAgc2NhbGVzID0gImZyZWUiKQpgYGAKCmBgYHtyfQpob3RlbHMgJT4lCiAgZ2dwbG90KGFlcyh5PWxlYWRfdGltZSwgeD1hcy5mYWN0b3IoaXNfY2FuY2VsZWQpKSkgKwogICAgZ2VvbV9ib3hwbG90KCkKYGBgCgpgYGB7cn0KaG90ZWxzICU+JQogIGdncGxvdChhZXMoeD0gZGVwb3NpdF90eXBlLCBncm91cD1pc19jYW5jZWxlZCkpICsgCiAgICBnZW9tX2JhcihhZXMoeSA9IC4ucHJvcC4uLCBmaWxsID0gZmFjdG9yKC4ueC4uKSksIHN0YXQ9ImNvdW50IikgKwogICAgZ2VvbV90ZXh0KGFlcyggbGFiZWwgPSBzY2FsZXM6OnBlcmNlbnQoLi5wcm9wLi4pLAogICAgICAgICAgICAgICAgICAgeT0gLi5wcm9wLi4gKSwgc3RhdD0gImNvdW50Iiwgdmp1c3QgPSAtLjUpICsKICAgIGxhYnMoeSA9ICJQZXJjZW50IiwgZmlsbD0iY3VzdG9tZXJfdHlwZSIpICsKICAgIGZhY2V0X2dyaWQofmlzX2NhbmNlbGVkKSArCiAgICBzY2FsZV95X2NvbnRpbnVvdXMobGFiZWxzID0gc2NhbGVzOjpwZXJjZW50KQpgYGAKCmBgYHtyfQpob3RlbHMgJT4lCiAgZ2dwbG90KGFlcyh4PSBjdXN0b21lcl90eXBlLCBncm91cD1pc19jYW5jZWxlZCkpICsgCiAgICBnZW9tX2JhcihhZXMoeSA9IC4ucHJvcC4uLCBmaWxsID0gZmFjdG9yKC4ueC4uKSksIHN0YXQ9ImNvdW50IikgKwogICAgZ2VvbV90ZXh0KGFlcyggbGFiZWwgPSBzY2FsZXM6OnBlcmNlbnQoLi5wcm9wLi4pLAogICAgICAgICAgICAgICAgICAgeT0gLi5wcm9wLi4gKSwgc3RhdD0gImNvdW50Iiwgdmp1c3QgPSAtLjUpICsKICAgIGxhYnMoeSA9ICJQZXJjZW50IiwgZmlsbD0iY3VzdG9tZXJfdHlwZSIpICsKICAgIGZhY2V0X2dyaWQofmlzX2NhbmNlbGVkKSArCiAgICBzY2FsZV95X2NvbnRpbnVvdXMobGFiZWxzID0gc2NhbGVzOjpwZXJjZW50KQpgYGAKCmBgYHtyfQpob3RlbHMgJT4lCiAgZmlsdGVyKGRheXNfaW5fd2FpdGluZ19saXN0ID4gMCkgJT4lCiAgZ2dwbG90KGFlcyh5PWRheXNfaW5fd2FpdGluZ19saXN0LCB4PWFzLmZhY3Rvcihpc19jYW5jZWxlZCkpKSsKICBnZW9tX2JveHBsb3QoKQpgYGAKCgoKCmBgYHtyfQpob3RlbHMgJT4lIAogIGFkZF9uX21pc3MoKSAlPiUgCiAgY291bnQobl9taXNzX2FsbCkKYGBgCgoKIyMjIDMuCkZpcnN0LCB3ZSB3aWxsIGRvIGEgY291cGxlIHRoaW5ncyB0byBnZXQgdGhlIGRhdGEgcmVhZHksIGluY2x1ZGluZyBtYWtpbmcgdGhlIG91dGNvbWUgYSBmYWN0b3IgKG5lZWRzIHRvIGJlIHRoYXQgd2F5IGZvciBsb2dpc3RpYyByZWdyZXNzaW9uKSwgcmVtb3ZpbmcgdGhlIHllYXIgdmFyaWFibGUgYW5kIHNvbWUgcmVzZXJ2YXRpb24gc3RhdHVzIHZhcmlhYmxlcywgYW5kIHJlbW92aW5nIG1pc3NpbmcgdmFsdWVzIChub3QgTlVMTHMgYnV0IHRydWUgbWlzc2luZyB2YWx1ZXMpLiBTcGxpdCB0aGUgZGF0YSBpbnRvIGEgdHJhaW5pbmcgYW5kIHRlc3Qgc2V0LCBzdHJhdGlmeWluZyBvbiB0aGUgb3V0Y29tZSB2YXJpYWJsZSwgaXNfY2FuY2VsZWQuIFNpbmNlIHdlIGhhdmUgYSBsb3Qgb2YgZGF0YSwgd2XigJlyZSBnb2luZyB0byBzcGxpdCB0aGUgZGF0YSA1MC81MCBiZXR3ZWVuIHRyYWluaW5nIGFuZCB0ZXN0LiBJIGhhdmUgYWxyZWFkeSBzZXQuc2VlZCgpIGZvciB5b3UuIEJlIHN1cmUgdG8gdXNlIGhvdGVsc19tb2QgaW4gdGhlIHNwbGl0dGluZy4KCmBgYHtyfQpob3RlbHNfbW9kIDwtIGhvdGVscyAlPiUgCiAgbXV0YXRlKGlzX2NhbmNlbGVkID0gYXMuZmFjdG9yKGlzX2NhbmNlbGVkKSkgJT4lIAogIG11dGF0ZShhY3Jvc3Mod2hlcmUoaXMuY2hhcmFjdGVyKSwgYXMuZmFjdG9yKSkgJT4lIAogIHNlbGVjdCgtYXJyaXZhbF9kYXRlX3llYXIsCiAgICAgICAgIC1yZXNlcnZhdGlvbl9zdGF0dXMsCiAgICAgICAgIC1yZXNlcnZhdGlvbl9zdGF0dXNfZGF0ZSkgJT4lIAogIGFkZF9uX21pc3MoKSAlPiUgCiAgZmlsdGVyKG5fbWlzc19hbGwgPT0gMCkgJT4lIAogIHNlbGVjdCgtbl9taXNzX2FsbCkKCnNldC5zZWVkKDQ5NCkKaG90ZWxfc3BsaXQgPC0gaW5pdGlhbF9zcGxpdChob3RlbHNfbW9kLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICBwcm9wID0gLjUpCmhvdGVsX3NwbGl0Cgpob3RlbF90cmFpbmluZyA8LSB0cmFpbmluZyhob3RlbF9zcGxpdCkKaG90ZWxfdGVzdGluZyA8LSB0ZXN0aW5nKGhvdGVsX3NwbGl0KQpgYGAKCiMjIyA0LgpJbiB0aGlzIG5leHQgc3RlcCwgd2UgYXJlIGdvaW5nIHRvIGRvIHRoZSBwcmUtcHJvY2Vzc2luZy4gVXN1YWxseSwgSSB3b27igJl0IHRlbGwgeW91IGV4YWN0bHkgd2hhdCB0byBkbyBoZXJlLCBidXQgZm9yIHlvdXIgZmlyc3QgZXhlcmNpc2UsIEnigJlsbCB0ZWxsIHlvdSB0aGUgc3RlcHMuCgpgYGB7cn0KaG90ZWxfcmVjaXBlIDwtIHJlY2lwZShpc19jYW5jZWxlZCB+IC4sICNzaG9ydC1jdXQsIC4gPSBhbGwgb3RoZXIgdmFycwogICAgICAgICAgICAgICAgICAgICAgIGRhdGEgPSBob3RlbF90cmFpbmluZykgJT4lIAogICMgUHJlLXByb2Nlc3Npbmc6CiAgIyBDcmVhdGUgaW5kaWNhdG9yIHZhcmlhYmxlcyBmb3IgY2hpbGRyZW4sIGJhYmllcywgYW5kIHByZXZpb3VzX2NhbmNlbGxhdGlvbnMKICBzdGVwX211dGF0ZV9hdChjaGlsZHJlbiwgYmFiaWVzLCBwcmV2aW91c19jYW5jZWxsYXRpb25zLAogICAgICAgICAgICAgICAgIGZuID0gfiBhcy5mYWN0b3IoKC4+MCkpCiAgICAgICAgICAgICAgICAgKSAlPiUKICBzdGVwX211dGF0ZV9hdChhZ2VudCwgY29tcGFueSwKICAgICAgICAgICAgICAgICBmbiA9IH4gYXMuZmFjdG9yKCguPT0gIk5VTEwiKSkKICAgICAgICAgICAgICAgICApICU+JQogIHN0ZXBfbXV0YXRlKGNvdW50cnkgPSBhcy5jaGFyYWN0ZXIoY291bnRyeSksCiAgICAgICAgICAgICAgY291bnRyeSA9IGZjdF9sdW1wX24oY291bnRyeSwgNSkpICU+JQogIHN0ZXBfbm9ybWFsaXplKGFsbF9wcmVkaWN0b3JzKCksIAogICAgICAgICAgICAgICAgIC1hbGxfbm9taW5hbCgpKSAlPiUKICBzdGVwX2R1bW15KGFsbF9ub21pbmFsKCksIAogICAgICAgICAgICAgLWFsbF9vdXRjb21lcygpKQoKYGBgCgoKYGBge3J9CmhvdGVsX3JlY2lwZSAlPiUgCiAgcHJlcChob3RlbF90cmFpbmluZykgJT4lCiAgIyB1c2luZyBiYWtlKG5ld19kYXRhID0gTlVMTCkgZ2l2ZXMgc2FtZSByZXN1bHQgYXMganVpY2UoKQogICMgYmFrZShuZXdfZGF0YSA9IE5VTEwpCiAganVpY2UoKQpgYGAKCiMjIyA1LgpJbiB0aGlzIHN0ZXAgd2Ugd2lsbCBzZXQgdXAgYSBMQVNTTyBtb2RlbCBhbmQgd29ya2Zsb3cuCkluIGdlbmVyYWwsIHdoeSB3b3VsZCB3ZSB3YW50IHRvIHVzZSBMQVNTTyBpbnN0ZWFkIG9mIHJlZ3VsYXIgbG9naXN0aWMgcmVncmVzc2lvbj8gKEhJTlQ6IHRoaW5rIGFib3V0IHdoYXQgaGFwcGVucyB0byB0aGUgY29lZmZpY2llbnRzKS4KCkJlY2F1c2UgTEFTU08gd2lsbCBzZWxlY3QgdGhlIG1vc3Qgc2lnbmlmaWNhbnQgdmFyaWFibGVzIGJ5IHNocmlua2luZyB0aGUgY29lZmZpY2llbnRzLCBhbmQgdGhlcmVmb3JlIHNlbGVjdCB0aGUgc3Vic2V0IG9mIHZhcmlhYmxlcyB0aGF0IG1heGltaXplcyBwcmVkaWN0aW9uIGFjY3VyYWN5LgoKRGVmaW5lIHRoZSBtb2RlbCB0eXBlLCBzZXQgdGhlIGVuZ2luZSwgc2V0IHRoZSBwZW5hbHR5IGFyZ3VtZW50IHRvIHR1bmUoKSBhcyBhIHBsYWNlaG9sZGVyLCBhbmQgc2V0IHRoZSBtb2RlLgpDcmVhdGUgYSB3b3JrZmxvdyB3aXRoIHRoZSByZWNpcGUgYW5kIG1vZGVsLgoKYGBge3J9CmhvdGVsX2xhc3NvX21vZCA8LSAKICAjIERlZmluZSBhIGxhc3NvIG1vZGVsIAogIGxvZ2lzdGljX3JlZyhtaXh0dXJlID0gMSkgJT4lIAogICMgU2V0IHRoZSBlbmdpbmUgdG8gImdsbSIgCiAgc2V0X2VuZ2luZSgiZ2xtbmV0IikgJT4lIAogICMgVGhlIHBhcmFtZXRlcnMgd2Ugd2lsbCB0dW5lLgogIHNldF9hcmdzKHBlbmFsdHkgPSB0dW5lKCkpICU+JSAKICAjIFVzZSAicmVncmVzc2lvbiIKICBzZXRfbW9kZSgiY2xhc3NpZmljYXRpb24iKQpgYGAKCmBgYHtyfQpob3RlbF9sYXNzb193ZiA8LSAKICAjIFNldCB1cCB0aGUgd29ya2Zsb3cKICB3b3JrZmxvdygpICU+JSAKICAjIEFkZCB0aGUgcmVjaXBlCiAgYWRkX3JlY2lwZShob3RlbF9yZWNpcGUpICU+JSAKICAjIEFkZCB0aGUgbW9kZWxpbmcKICBhZGRfbW9kZWwoaG90ZWxfbGFzc29fbW9kKQpgYGAKCiMjIyA2LgpJbiB0aGlzIHN0ZXAsIHdl4oCZbGwgdHVuZSB0aGUgbW9kZWwgYW5kIGZpdCB0aGUgbW9kZWwgdXNpbmcgdGhlIGJlc3QgdHVuaW5nIHBhcmFtZXRlciB0byB0aGUgZW50aXJlIHRyYWluaW5nIGRhdGFzZXQuCgpDcmVhdGUgYSA1LWZvbGQgY3Jvc3MtdmFsaWRhdGlvbiBzYW1wbGUuCgpgYGB7cn0KIyBTZXQgc2VlZApzZXQuc2VlZCg0OTQpICMgZm9yIHJlcHJvZHVjaWJpbGl0eQojIENyZWF0ZSBhIDUtZm9sZCBjcm9zcy12YWxpZGF0aW9uIHNhbXBsZQpob3RlbF9jdiA8LSB2Zm9sZF9jdihob3RlbF90cmFpbmluZywgdiA9IDUpCmBgYAoKVXNlIHRoZSBncmlkX3JlZ3VsYXIoKSBmdW5jdGlvbiB0byBjcmVhdGUgYSBncmlkIG9mIDEwIHBvdGVudGlhbCBwZW5hbHR5IHBhcmFtZXRlcnMgKHdl4oCZcmUga2VlcGluZyB0aGlzIHNvcnQgb2Ygc21hbGwgYmVjYXVzZSB0aGUgZGF0YXNldCBpcyBwcmV0dHkgbGFyZ2UpLiBVc2UgdGhhdCB3aXRoIHRoZSA1LWZvbGQgY3YgZGF0YSB0byB0dW5lIHRoZSBtb2RlbC4KCmBgYHtyfQpwZW5hbHR5X2dyaWQgPC0gZ3JpZF9yZWd1bGFyKHBlbmFsdHkoKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICBsZXZlbHMgPSAxMCkKYGBgCgpVc2UgdGhlIHR1bmVfZ3JpZCgpIGZ1bmN0aW9uIHRvIGZpdCB0aGUgbW9kZWxzIHdpdGggZGlmZmVyZW50IHR1bmluZyBwYXJhbWV0ZXJzIHRvIHRoZSBkaWZmZXJlbnQgY3Jvc3MtdmFsaWRhdGlvbiBzZXRzLgoKYGBge3J9CmhvdGVsX2xhc3NvX3R1bmUgPC0gCiAgaG90ZWxfbGFzc29fd2YgJT4lIAogIHR1bmVfZ3JpZCgKICAgIHJlc2FtcGxlcyA9IGhvdGVsX2N2LAogICAgZ3JpZCA9IHBlbmFsdHlfZ3JpZAogICAgKQpgYGAKClVzZSB0aGUgY29sbGVjdF9tZXRyaWNzKCkgZnVuY3Rpb24gdG8gY29sbGVjdCBhbGwgdGhlIG1ldHJpY3MgZnJvbSB0aGUgcHJldmlvdXMgc3RlcCBhbmQgY3JlYXRlIGEgcGxvdCB3aXRoIHRoZSBhY2N1cmFjeSBvbiB0aGUgeS1heGlzIGFuZCB0aGUgcGVuYWx0eSB0ZXJtIG9uIHRoZSB4LWF4aXMuIFB1dCB0aGUgeC1heGlzIG9uIHRoZSBsb2cgc2NhbGUuCgpgYGB7cn0KaG90ZWxfbGFzc29fdHVuZSAlPiUgCiAgY29sbGVjdF9tZXRyaWNzKCkgJT4lIAogIGZpbHRlcigubWV0cmljID09ICJhY2N1cmFjeSIpIApgYGAKCmBgYHtyfQojIFZpc3VhbGl6ZSBhY2N1cmFjeSB2cy4gcGVuYWx0eQpob3RlbF9sYXNzb190dW5lICU+JSAKICBjb2xsZWN0X21ldHJpY3MoKSAlPiUgCiAgZmlsdGVyKC5tZXRyaWMgPT0gImFjY3VyYWN5IikgJT4lIAogIGdncGxvdChhZXMoeCA9IHBlbmFsdHksIHkgPSBtZWFuKSkgKwogIGdlb21fcG9pbnQoKSArCiAgZ2VvbV9saW5lKCkgKwogIHNjYWxlX3hfbG9nMTAoCiAgIGJyZWFrcyA9IHNjYWxlczo6dHJhbnNfYnJlYWtzKCJsb2cxMCIsIGZ1bmN0aW9uKHgpIDEwXngpLAogICBsYWJlbHMgPSBzY2FsZXM6OnRyYW5zX2Zvcm1hdCgibG9nMTAiLHNjYWxlczo6bWF0aF9mb3JtYXQoMTBeLngpKSkgKwogIGxhYnMoeCA9ICJwZW5hbHR5IiwgeSA9ICJybXNlIikKYGBgCgpVc2UgdGhlIHNlbGVjdF9iZXN0KCkgZnVuY3Rpb24gdG8gZmluZCB0aGUgYmVzdCB0dW5pbmcgcGFyYW1ldGVyLCBmaXQgdGhlIG1vZGVsIHVzaW5nIHRoYXQgdHVuaW5nIHBhcmFtZXRlciB0byB0aGUgZW50aXJlIHRyYWluaW5nIHNldCAoSElOVDogZmluYWxpemVfd29ya2Zsb3coKSBhbmQgZml0KCkpLCBhbmQgZGlzcGxheSB0aGUgbW9kZWwgcmVzdWx0cyB1c2luZyBwdWxsX3dvcmtmbG93X2ZpdCgpIGFuZCB0aWR5KCkuIEFyZSB0aGVyZSBzb21lIHZhcmlhYmxlcyB3aXRoIGNvZWZmaWNpZW50cyBvZiAwPwpgYGB7cn0KYmVzdF9wYXJhbSA8LSBob3RlbF9sYXNzb190dW5lICU+JSAKICBzZWxlY3RfYmVzdChtZXRyaWMgPSAiYWNjdXJhY3kiKQpiZXN0X3BhcmFtCgpob3RlbF9sYXNzb19maW5hbF93ZiA8LSBob3RlbF9sYXNzb193ZiAlPiUgCiAgZmluYWxpemVfd29ya2Zsb3coYmVzdF9wYXJhbSkKCmhvdGVsX2xhc3NvX2ZpbmFsX21vZCA8LSBob3RlbF9sYXNzb19maW5hbF93ZiAlPiUgCiAgZml0KGRhdGEgPSBob3RlbF90cmFpbmluZykKCmhvdGVsX2xhc3NvX2ZpbmFsX21vZCAlPiUgCiAgcHVsbF93b3JrZmxvd19maXQoKSAlPiUgCiAgdGlkeSgpIApgYGAKCmBtYXJrZXRfc2VnbWVudF9Hcm91cHNgLCBgZGlzdHJpYnV0aW9uX2NoYW5uZWxfVW5kZWZpbmVkYCwgYGFzc2lnbmVkX3Jvb21fdHlwZV9MYCwgYGFzc2lnbmVkX3Jvb21fdHlwZV9QYCBhbGwgaGF2ZSBjb2VmZmljaWVudHMgZXF1YWwgdG8gMC4KCiMjIyA3LgpOb3cgdGhhdCB3ZSBoYXZlIGEgbW9kZWwsIGxldOKAmXMgZXZhbHVhdGUgaXQgYSBiaXQgbW9yZS4gQWxsIHdlIGhhdmUgbG9va2VkIGF0IHNvIGZhciBpcyB0aGUgY3Jvc3MtdmFsaWRhdGVkIGFjY3VyYWN5IGZyb20gdGhlIHByZXZpb3VzIHN0ZXAuCgpDcmVhdGUgYSB2YXJpYWJsZSBpbXBvcnRhbmNlIGdyYXBoLiBXaGljaCB2YXJpYWJsZXMgc2hvdyB1cCBhcyB0aGUgbW9zdCBpbXBvcnRhbnQ/IEFyZSB5b3Ugc3VycHJpc2VkPwpgYGB7cn0KIyBWaXN1YWxpemUgdmFyaWFibGUgaW1wb3J0YW5jZQpob3RlbF9sYXNzb19maW5hbF9tb2QgJT4lIAogIHB1bGxfd29ya2Zsb3dfZml0KCkgJT4lIAogIHZpcCgpCmBgYAoKSSBhbSBzdXJwcmlzZWQgdGhhdCBgcmVzZXJ2ZWRfcm9vbV90eXBlX1BgIGlzIHRoZSBtb3N0IGltcG9ydGFudCBmYWN0b3IsIGFuZCBJIGFtIGFsc28gc3VycHJpc2VkIHRoYXQgaW4gZ2VuZXJhbCByb29tIHR5cGUgaXMgYW4gaW1wb3J0YW50IGZhY3RvciwgYW5kIHRoYXQgYSBub24gcmVmdW5kYWJsZSBkZXBvc2l0IHR5cGUgYWN0dWFsbHkgaGFzIGEgcG9zaXRpdmUgY29lZmZpY2llbnQuCgpVc2UgdGhlIGxhc3RfZml0KCkgZnVuY3Rpb24gdG8gZml0IHRoZSBmaW5hbCBtb2RlbCBhbmQgdGhlbiBhcHBseSBpdCB0byB0aGUgdGVzdGluZyBkYXRhLiBSZXBvcnQgdGhlIG1ldHJpY3MgZnJvbSB0aGUgdGVzdGluZyBkYXRhIHVzaW5nIHRoZSBjb2xsZXRfbWV0cmljcygpIGZ1bmN0aW9uLiBIb3cgZG8gdGhleSBjb21wYXJlIHRvIHRoZSBjcm9zcy12YWxpZGF0ZWQgbWV0cmljcz8KCmBgYHtyfQpob3RlbF9sYXNzb190ZXN0IDwtIGhvdGVsX2xhc3NvX2ZpbmFsX3dmICU+JSAKICBsYXN0X2ZpdChob3RlbF9zcGxpdCkKCmhvdGVsX2xhc3NvX3Rlc3QgJT4lIAogIGNvbGxlY3RfbWV0cmljcygpCmBgYApUaGV5IGFyZSBzaW1pbGFyIHRvIHRoZSBjcm9zcyB2YWxpZGF0ZWQgbWV0cmljcy4KClVzZSB0aGUgY29sbGVjdF9wcmVkaWN0aW9ucygpIGZ1bmN0aW9uIHRvIGZpbmQgdGhlIHByZWRpY3RlZCBwcm9iYWJpbGl0aWVzIGFuZCBjbGFzc2VzIGZvciB0aGUgdGVzdCBkYXRhLiBTYXZlIHRoaXMgdG8gYSBuZXcgZGF0YXNldCBjYWxsZWQgcHJlZHMuIFRoZW4sIHVzZSB0aGUgY29uZl9tYXQoKSBmdW5jdGlvbiBmcm9tIGRpYWxzIChwYXJ0IG9mIHRpZHltb2RlbHMpIHRvIGNyZWF0ZSBhIGNvbmZ1c2lvbiBtYXRyaXggc2hvd2luZyB0aGUgcHJlZGljdGVkIGNsYXNzZXMgdnMuIHRoZSB0cnVlIGNsYXNzZXMuIFdoYXQgaXMgdGhlIHRydWUgcG9zaXRpdmUgcmF0ZSAoc2Vuc2l0aXZpdHkpPyBXaGF0IGlzIHRoZSB0cnVlIG5lZ2F0aXZlIHJhdGUgKHNwZWNpZmljaXR5KT8gU2VlIHRoaXMgV2lraXBlZGlhIHJlZmVyZW5jZSBpZiB5b3UgKGxpa2UgbWUpIHRlbmQgdG8gZm9yZ2V0IHRoZXNlIGRlZmluaXRpb25zLgoKYGBge3J9CnByZWRzIDwtIGNvbGxlY3RfcHJlZGljdGlvbnMoaG90ZWxfbGFzc29fdGVzdCkgCgpwcmVkcyAlPiUKICBjb25mX21hdChpc19jYW5jZWxlZCwgLnByZWRfY2xhc3MpCmBgYAoKVGhlIHRydWUgcG9zaXRpdmUgcmF0ZSAoc2Vuc2l0aXZpdHkpIGlzICQxNDAzMi8oMTQwMzIrODAwNClcYXBwcm94IDYzLjY4XCUkLCBhbmQgdGhlIHRydWUgbmVnYXRpdmUgcmF0ZSAoc3BlY2lmaWNpdHkpIGlzICQzNDQ5My8oMzQ0OTMrMzE2NClcYXBwcm94IDkxLjYwXCUkCgpVc2UgdGhlIHByZWRzIGRhdGFzZXQgeW91IGp1c3QgY3JlYXRlZCB0byBjcmVhdGUgYSBkZW5zaXR5IHBsb3Qgb2YgdGhlIHByZWRpY3RlZCBwcm9iYWJpbGl0aWVzIG9mIGNhbmNlbGluZyAodGhlIHZhcmlhYmxlIGlzIGNhbGxlZCAucHJlZF8xKSwgZmlsbGluZyBieSBpc19jYW5jZWxlZC4gVXNlIGFuIGFscGhhID0gLjUgYW5kIGNvbG9yID0gTkEgaW4gdGhlIGdlb21fZGVuc2l0eSgpLiBBbnN3ZXIgdGhlc2UgcXVlc3Rpb25zOiAKCmBgYHtyfQpwcmVkcyAlPiUKICBnZ3Bsb3QoYWVzKHggPSAucHJlZF8xLCBmaWxsID0gaXNfY2FuY2VsZWQpKSArCiAgZ2VvbV9kZW5zaXR5KGFscGhhPTAuNSwgY29sb3IgPSBOQSkKYGBgCgoKIyMjIyBhLiAKV2hhdCB3b3VsZCB0aGlzIGdyYXBoIGxvb2sgbGlrZSBmb3IgYSBtb2RlbCB3aXRoIGFuIGFjY3VyYWN5IHRoYXQgd2FzIGNsb3NlIHRvIDE/IAoKVGhlIHR3byBkZW5zaXR5IGN1cnZlcyB3b3VsZCBiZSBhbG1vc3Qgc2VwYXJhdGVkIGluc3RlYWQgb2YgaGF2aW5nIGEgbG90IG9mIG92ZXJsYXBwZWQgcmVnaW9uLgoKIyMjIyBiLiAKT3VyIHByZWRpY3Rpb25zIGFyZSBjbGFzc2lmaWVkIGFzIGNhbmNlbGVkIGlmIHRoZWlyIHByZWRpY3RlZCBwcm9iYWJpbGl0eSBvZiBjYW5jZWxpbmcgaXMgZ3JlYXRlciB0aGFuIC41LiBJZiB3ZSB3YW50ZWQgdG8gaGF2ZSBhIGhpZ2ggdHJ1ZSBwb3NpdGl2ZSByYXRlLCBzaG91bGQgd2UgbWFrZSB0aGUgY3V0b2ZmIGZvciBwcmVkaWN0ZWQgYXMgY2FuY2VsZWQgaGlnaGVyIG9yIGxvd2VyIHRoYW4gLjU/IAoKV2Ugc2hvdWxkIG1ha2UgdGhlIGN1dG9mZiBoaWdoZXIgdGhhbiAwLjUsIHNvIHRoYXQgaXQgYmVjb21lcyBtb3JlIGxpa2VseSB0byBwcmVkaWN0IGNhbmNlbGluZywgYW5kIG1vcmUgdHJ1bHkgY2FuY2VsZWQgY2FzZXMgd291bGQgYmUgcHJlZGljdGVkIHRvIGJlIGNhbmNlbGVkLgoKIyMjIyBjLiAKV2hhdCBoYXBwZW5zIHRvIHRoZSB0cnVlIG5lZ2F0aXZlIHJhdGUgaWYgd2UgdHJ5IHRvIGdldCBhIGhpZ2hlciB0cnVlIHBvc2l0aXZlIHJhdGU/CgpUaGUgdHJ1ZSBuZWdhdGl2ZSByYXRlIHdvdWxkIGJlIGxvd2VyIGJlY2F1c2UgbW9yZSB1bmNhbmNlbGVkIGNhc2VzIHdpbGwgYmUgY2xhc3NpZmllZCBhcyBjYW5jZWxlZCBpZiB3ZSB0cnkgdG8gZ2V0IGEgaGlnaGVyIHRydWUgcG9zaXRpdmUgcmF0ZS4KCiMjIyA4LgpMZXTigJlzIHNheSB0aGF0IHRoaXMgbW9kZWwgaXMgZ29pbmcgdG8gYmUgYXBwbGllZCB0byBib29raW5ncyAxNCBkYXlzIGluIGFkdmFuY2Ugb2YgdGhlaXIgYXJyaXZhbCBhdCBlYWNoIGhvdGVsLCBhbmQgc29tZW9uZSB3aG8gd29ya3MgZm9yIHRoZSBob3RlbCB3aWxsIG1ha2UgYSBwaG9uZSBjYWxsIHRvIHRoZSBwZXJzb24gd2hvIG1hZGUgdGhlIGJvb2tpbmcuIER1cmluZyB0aGlzIHBob25lIGNhbGwsIHRoZXkgd2lsbCB0cnkgdG8gYXNzdXJlIHRoYXQgdGhlIHBlcnNvbiB3aWxsIGJlIGtlZXBpbmcgdGhlaXIgcmVzZXJ2YXRpb24gb3IgdGhhdCB0aGV5IHdpbGwgYmUgY2FuY2VsaW5nIGluIHdoaWNoIGNhc2UgdGhleSBjYW4gZG8gdGhhdCBub3cgYW5kIHN0aWxsIGhhdmUgdGltZSB0byBmaWxsIHRoZSByb29tLiBIb3cgc2hvdWxkIHRoZSBob3RlbCBnbyBhYm91dCBkZWNpZGluZyB3aG8gdG8gY2FsbD8gSG93IGNvdWxkIHRoZXkgbWVhc3VyZSB3aGV0aGVyIGl0IHdhcyB3b3J0aCB0aGUgZWZmb3J0IHRvIGRvIHRoZSBjYWxsaW5nPyBDYW4geW91IHRoaW5rIG9mIGFub3RoZXIgd2F5IHRoZXkgbWlnaHQgdXNlIHRoZSBtb2RlbD8KCkFjY29yZGluZyB0byB0aGUgb3V0Y29tZSBhbmQgVklQIG9mIHRoaXMgbW9kZWwsIHRoZXkgc2hvdWxkIGNhbGwgdGhlIHBlb3BsZSB3aG8gcmVzZXJ2ZSByb29tIHR5cGUgUCwgd2hvc2UgZGVwb3NpdCB0eXBlIGlzIG5vbi1yZWZ1bmRhYmxlLCBhbmQgd2hvIGRpZCBoYXZlIHByZXZpb3VzIGNhbmNlbGxhdGlvbnMgd2l0aCB0aGUgaG90ZWwuIFRoZXkgY2FuIGFsc28gaW5wdXQgZWFjaCBjdXN0b21lcidzIGluZm9ybWF0aW9uIGludG8gdGhlIG1vZGVsLCBhbmQgcHJlZGljdCB3aGV0aGVyIHRoZXkgd291bGQgY2FuY2VsIGFjY29yZGluZyB0byB0aGUgbW9kZWwsIGFuZCBjYWxsIHRoZSBwZW9wbGUgd2hvIGFyZSBwcmVkaWN0ZWQgdG8gY2FuY2VsLiBBbHNvLCBzaW5jZSByZXNlcnZlZCByb29tIHR5cGUgYW5kIGFzc2lnbmVkIHJvb20gdHlwZSBhcmUgYm90aCBpbXBvcnRhbnQgd2hlbiBkZXRlcm1pbmluZyB3aGV0aGVyIHRoZSBjdXN0b21lciB3b3VsZCBjYW5jZWwsIHRoZSBob3RlbCBzaG91bGQgbWFrZSBhIGNhbGwgaWYgdGhleSBuZWVkIHRvIGNoYW5nZSB0aGUgcm9vbSB0eXBlIGZvciBhIGN1c3RvbWVyLiAKCkFub3RoZXIgd2F5IHRoZXkgbWlnaHQgdXNlIHRoZSBtb2RlbCBpcyB0byBlc3RpbWF0ZSBob3cgbWFueSByZXNlcnZhdGlvbnMgbWlnaHQgYmUgY2FuY2VsZWQgZm9yIGVhY2ggZGF5LCBzbyB0aGF0IHRoZXkgY291bGQgYWRqdXN0IHRoZSBudW1iZXIgb2YgZW1wbG95ZWVzIHdvcmtpbmcgdGhhdCBkYXkuCgojIyMgOS4KSG93IG1pZ2h0IHlvdSBnbyBhYm91dCBxdWVzdGlvbmluZyBhbmQgZXZhbHVhdGluZyB0aGUgbW9kZWwgaW4gdGVybXMgb2YgZmFpcm5lc3M/IEFyZSB0aGVyZSBhbnkgcXVlc3Rpb25zIHlvdSB3b3VsZCBsaWtlIHRvIGFzayBvZiB0aGUgcGVvcGxlIHdobyBjb2xsZWN0ZWQgdGhlIGRhdGE/CgpJIHdvdWxkIG1vc3QgbGlrZWx5IHF1ZXN0aW9uIHRoZSBpbmNsdXNpb24gb2YgY291bnRyeSBvZiBvcmlnaW4gZm9yIGVhY2ggY3VzdG9tZXIgaW4gdGhpcyBtb2RlbC4gSSBmZWVsIGxpa2UgY2FuY2VsaW5nIHJlc2VydmF0aW9ucyBpcyBhIG1vcmUgcGVyc29uYWwgdGhpbmcsIGFuZCBpZiB0aGlzIG1vZGVsIGluZGljYXRlcyB0aGF0IHBlb3BsZSBmcm9tIGNlcnRhaW4gY291bnRyaWVzIGFyZSBtb3JlIGxpa2VseSB0byBjYW5jZWwsIGl0IHdvdWxkIGNhdXNlIGZhbHNlIHN0ZXJlb3R5cGUgYWdhaW5zdCBwZW9wbGUgZnJvbSBjZXJ0YWluIGNvdW50cmllcyB3aGVuIHRoZXkgYXJlIGJvb2tpbmcgaG90ZWxzLCBhbmQgdGhhdCBpcyBub3QgZmFpci4KCk9uZSBxdWVzdGlvbiBJIHdvdWxkIGxpa2UgdG8gYXNrIGlzIHdoYXQgbWVhc3VyZXMgaGF2ZSB0aGV5IHRha2VuIHRvIGVuc3VyZSB0aGF0IHRoZWlyIHNhbXBsZSBpcyBnZW5lcmFsIGVub3VnaCBhbmQgd2hhdCBraW5kIG9mIHNlbGVjdGlvbiBiaWFzIG1pZ2h0IGJlIGludm9sdmUgaW4gdGhlIGRhdGEuCgojIyBFeGVyY2lzZSA0IEJpYXMgYW5kIEZhaXJuZXNzCkxpc3RlbiB0byBEci4gUmFjaGVsIFRob21hc+KAmXMgQmlhcyBhbmQgRmFpcm5lc3MgbGVjdHVyZS4gV3JpdGUgYSBicmllZiBwYXJhZ3JhcGggcmVmbGVjdGluZyBvbiBpdC4gWW91IG1pZ2h0IGFsc28gYmUgaW50ZXJlc3RlZCBpbiByZWFkaW5nIHRoZSBQcm9QdWJsaWNhIGFydGljbGUgRHIuIFRob21hcyByZWZlcmVuY2VzIGFib3V0IHVzaW5nIGEgdG9vbCBjYWxsZWQgQ09NUEFTIHRvIHByZWRpY3QgcmVjaWRpdmlzbS4gU29tZSBxdWVzdGlvbnMvaWRlYXMgeW91IG1pZ2h0IGtlZXAgaW4gbWluZDoKCkRpZCB5b3UgaGVhciBhbnl0aGluZyB0aGF0IHN1cnByaXNlZCB5b3U/CgpJIHdhcyBzdXJwcmlzZWQgdGhhdCBzb21lIGJpZyBlbnRlcnByaXNlcyBzdGlsbCBwcmFjdGljZSBiaWFzZWQgbWFjaGluZSBsZWFybmluZyBtb2RlbHMgd2hlbiByZWxlYXNpbmcgYWR2ZXJ0aXNlbWVudHMgZXZlbiBhZnRlciB0aGV5IGJlY29tZSBhd2FyZSBvZiB0aGUgYmlhcyB0aGF0IHRoZXkgY2F1c2VkLgoKV2h5IGlzIGl0IGltcG9ydGFudCB0aGF0IHdlIHBheSBhdHRlbnRpb24gdG8gYmlhcyBhbmQgZmFpcm5lc3Mgd2hlbiBzdHVkeWluZyBkYXRhIHNjaWVuY2U/CgpCZWNhdXNlIGl0IGlzIGVhc3kgdG8gZ2VuZXJhbGl6ZSBwZW9wbGUgYW5kIGNhdXNlIHN0ZXJlb3R5cGUgb3IgZGlzY3JpbWluYXRpb24gYWdhaW5zdCBjZXJ0YWluIGdyb3VwcyBvZiBwZW9wbGUgd2hlbiB3ZSB1c2UgbWFjaGluZSBsZWFybmluZyBtb2RlbHMuIFRoZXNlIG1vZGVscyBhcmUgdXNlZCB3aWRlbHksIGFuZCBpZiB0aGV5IGFyZSBtaXN1c2VkIHRvIGNhdXNlIGJpYXNlcyBhbmQgdW5mYWlybmVzcywgaXQgd291bGQgaHVydCBtYW55IHBlb3BsZS4gQWxzbywgYmlhcyBtaWdodCBhcmlzZSBldmVuIHdoZW4gd2UgYXJlIGNvbGxlY3RpbmcgZGF0YSwgc28gd2UgaGF2ZSB0byBhY2tub3dsZWRnZSBwb3NzaWJsZSBiaWFzZXMgdGhhdCBtaWdodCBiZSBjYXVzZWQgaW4gb3VyIGRhdGEgY29sbGVjdGlvbiBwcm9jZXNzLgoKSXMgdGhlcmUgYSB0eXBlIG9mIGJpYXMgRHIuIFRob21hcyBkaXNjdXNzZWQgdGhhdCB3YXMgbmV3IHRvIHlvdT8gQ2FuIHlvdSB0aGluayBhYm91dCBwbGFjZXMgeW91IGhhdmUgc2VlbiB0aGVzZSB0eXBlcyBvZiBiaWFzZXM/CgpBZ2dyZWdhdGVkIGJpYXMgaXMgbmV3IHRvIG1lLiBJIGNvdWxkbid0IHRoaW5rIG9mIGFuIGV4YW1wbGUgd2hlcmUgSSBzZWUgdGhpcyB0eXBlIG9mIGJpYXMsIGJ1dCBJIGd1ZXNzIGEgc2NlbmFyaW8gd2hlcmUgdGhlcmUgZXhpc3RzIGFnZ3JlZ2F0ZWQgYmlhcyBtaWdodCBiZSBhIGRhdGFzZXQgd2l0aCBkaWZmZXJlbnQgZ3JvdXBzIHdoZXJlIHRoZSBjb3JyZWxhdGlvbiBvZiB0aGUgdHdvIHZhcmlhYmxlcyBvZiBpbnRlcmVzdCBhcmUgc21hbGwgd2l0aGluIGVhY2ggZ3JvdXAsIGJ1dCBiZWNvbWVzIGJpZyBpbiB0aGUgd2hvbGUgZGF0YXNldC4gCgogCg==